1. Field of the Invention
The present invention relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, and more particularly, relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, according to Hybrid Vector Quantization (HVQ) system.
2. Description of Related Art
According to JPEG (Joint Photographic Expert Group) system, 8 times 8 pixel blocks are converted to DC (direct current) value and each coefficient value of from base to 63 times frequency by two dimensional DCT (discrete cosine transform), and information amount is reduced by quantizing the coefficient value in a different quantization width within no reduction of image quality utilizing frequency components of natural images which are gathered in a low frequency range, and then Huffman encoding is carried out.
According to HVQ system, which is a kind of mean value separation type block encoding same as JPEG, adaptive orthogonal transform (AOT) which is an intermediate system between a vector quantization and orthogonal transform encoding is used as a compression principle. AOT is a system in which the minimum number of non-orthogonal basis is selected from nests of the basis corresponding to a code book of vector quantization and the objective blocks become close to the desired and allowable error xe2x80x9cZxe2x80x9d. According to the HVQ system, decoding is quickly carried because a decoding operation can be done in the form of integer. Natural images and artificial images (animation images, CG images) can be compressed in high image quality, because there are not mosquito and block noise, which are particularly generated in JPEG, and false contour, which is particularly generated in GIF. The invention relates to a method for further improving the image quality and for carrying out the coding operation at a higher speed in the HVQ system.
The applicants of the invention have proposed an image encoding/decoding method in accordance with the HVQ system utilizing self-similarity of images in Japanese Patent Application No. 189239/98. The contents of such proposal will be explained as follows. In the disclosure, a sign  less than a greater than  means vector xe2x80x9caxe2x80x9d or block xe2x80x9caxe2x80x9d, a sign ∥a∥ means norm of the vector xe2x80x9caxe2x80x9d, and a sign  less than axc2x7b greater than  means inner product of vectors a and b. Further, vectors and blocks in drawings and [numbers] are represented by block letters.
FIG. 1 is a block diagram showing a conventional image encoder. In FIG. 1, 11 is an original image memory for storing an original image data, 12 is a DC value production unit for seeking a block average (DC) value per each pixel block (4 times 4 pixel) of the original image data, 13 is a differential PCM encoding unit (DPCM) for carrying out a differential predict encoding per each DC value, 14 is inverse DPCM encoding unit for decoding each DC value from the differential PCM encoding, 15 is a DC image memory for storing a decoded DC image, 16 is a DC nest production unit for cutting off the DC nest of a desired size from a part of the DC image, and 17 is a DC nest memory for storing the DC nest.
Further, 18 is a subtractor for separating a corresponding decoding DC value xe2x80x9cDCJxe2x80x9d from a target image block  less than RJ greater than  to be encoded, 19 is a differential vector buffer for storing a differential vector  less than dJ greater than  which is DC separated, 20 is an extracted block buffer for storing a base extraction block  less than Ui greater than  of 4 times 4 pixels which is down-sampled from the DC nest, 21 is an equilibrator for seeking a block mean value ai of the base extraction block  less than Ui greater than , 22 is a subtractor for separating the block means value ai from the base extraction block  less than Ui greater than , 23 is an extracted vector buffer for storing the base extraction block  less than Ui greater than  which is separated by the mean value, 24 is an adaptive orthogonal transform (AOT) processing unit for producing an orthogonal basis xcex1k  less than ukxe2x80x2 greater than  (k=1xcx9cm) to search the DC nest to make the differential vector  less than dj greater than  closer to the allowable error Z, where a square norm ∥dj∥2 of the differential vector is over the allowable error Z, 25 is a coefficient transform unit for seeking an expanding square coefficient xcex2k which is multiplied by a non-orthogonal basis vector  less than uk greater than  (k=1xcx9cm) per the produced orthogonal basis xcex1k  less than ukxe2x80x2 greater than  (k=1xcx9cm) to produce an equivalent non-orthogonal basis xcex2k  less than uk greater than  (k=1xcx9cm, and 26 is an encoding unit by Huffman coding, run length coding or fixed length coding system for the compression encoding of information such as DPCM encoding of the DC value or the non-orthogonal basis xcex2k  less than uk greater than .
In the DC value production unit 12, the block mean value of 4 times 4 pixels is provided in which the first decimal place is rounded off or down. In the DPCM 13, where the DC value of row J and column T is shown by the DCJ, I, a predictive value DCJ, Ixe2x80x2 of the DCJ,I is provided by the formula, DCJ, Ixe2x80x2=(DCJ, Ixe2x88x921+DCJxe2x88x921, I)/2, and its predictive error (xcex94 DCJ, I=DCJ, Ixe2x88x92DCJ, Ixe2x80x2) is linear-quantized by a quantization coefficient Q(Z) and is output. The quantization coefficient Q(Z) corresponds to the allowable error Z and is variable within the range of 1 to 8 according to the allowable error Z.
In the DC nest production unit 16, the DC nest is prepared by copying the range of vertical 39xc3x97horizontal 71 from the DC image. It is preferred that the DC nest includes more alternating current components because it is used as a codebook. Therefore, it is prepared by copying such the range that the sum of absolute values of difference between the DC values adjacent to each other in a plurality of the extracted ranges become maximum.
In making down-samples of the base extraction block  less than Ui greater than , a vertex per one DC value in vertical and horizontal section is set to (px, py) xcex5 [0, 63]xc3x97[0, 31] and a distance of its sub-samples is set to 4 kinds of (sx, sy) xcex5 {(1, 1), (1, 2), (2, 1), (2, 2) }. Accordingly, the total numbers of the base extraction blocks  less than Ui greater than  are N (=8192) and are referred by an index counter xe2x80x9cixe2x80x9d from the AOT 24. Behavior of conventional adaptive orthogonal transform processing unit 24 will be explained below.
FIG. 2 is a flow chart of conventional adaptive orthogonal transform processing and FIG. 3 is an image drawing of the processing. In FIG. 2, it is input in the processing that the square norm ∥dj∥2 of the differential vector is more than Z. In step S121, the square norm ∥dj∥2 of the differential vector is set in a resister E. A basis number counter is initialized to k=1. In step S122, much value ( e.g. 100,000) is set in a minimum value holding resister Exe2x80x2. In step S123, an index counter of the base extraction block  less than Ui greater than  is initialized to i=0. By these steps, the initial address and distance of sub-samples in the DC nest are set to (px, py)=(0, 0) and (sx, sy)=(1, 1), respectively.
In step S124, the base extraction vector  less than ui greater than  is produced by separating the block mean value ai from the base extraction blocks  less than Ui greater than . Since the operation or calculation is carried out under the accuracy of integer level, any value of first decimal place in the block mean value ai is rounded off or down. In step S125, the base extraction vector  less than ui greater than  is subjected to orthogonal transform processing to be converted to the orthogonal basis vector  less than ukxe2x80x2 greater than , if necessary (k greater than 1).
FIG. 3 (A) and (B) are image drawings of the orthogonal transform processing. In FIG. 3 (A), the first base extraction vector  less than u1 greater than  can be the first basis vector  less than u1xe2x80x2 greater than  as it is.
Then, the second base extraction vector  less than u2 greater than  is subjected to orthogonal transform processing to be converted to the second basis vector  less than u2xe2x80x2 greater than  in accordance with the following method. That is, a shadow of the second base extraction vector  less than u2 greater than  projected on the first basis vector  less than u1xe2x80x2 greater than  is represented by the formula (1).
[Numeral 1]                                          "LeftDoubleBracketingBar"                          u              2                        "RightDoubleBracketingBar"                    ⁢          cos          ⁢                      xe2x80x83                    ⁢          θ                =                                                            ⟨                                                      u                    1                    xe2x80x2                                    ·                                      u                    2                                                  ⟩                                            "LeftDoubleBracketingBar"                                  u                  1                  xe2x80x2                                "RightDoubleBracketingBar"                                      ⁢                          xe2x80x83                        ∵                          ⟨                                                u                  1                  xe2x80x2                                ·                                  u                  2                                            ⟩                                =                                    "LeftDoubleBracketingBar"                              u                1                xe2x80x2                            "RightDoubleBracketingBar"                        ⁢                          xe2x80x83                        ⁢                          "LeftDoubleBracketingBar"                              u                2                            "RightDoubleBracketingBar"                        ⁢            cos            ⁢                          xe2x80x83                        ⁢            θ                                              (        1        )            
Accordingly, the second orthogonal vector  less than u2xe2x80x2 greater than  is obtained by subtracting the vector of the projected shadow from the second base extraction vector  less than u2 greater than .
[Numeral 2]                              u          2          xe2x80x2                =                              u            2                    -                                                    ⟨                                                      u                    1                    xe2x80x2                                    ·                                      u                    2                                                  ⟩                                            "LeftDoubleBracketingBar"                                  u                  1                  xe2x80x2                                "RightDoubleBracketingBar"                                      ⁢                          xe2x80x83                        ⁢                                          u                1                xe2x80x2                                            "LeftDoubleBracketingBar"                                  u                  1                  xe2x80x2                                "RightDoubleBracketingBar"                                                                        (        2        )            
In FIG. 3(B), the third base extraction vector  less than u3 greater than  is subjected to orthogonal transform processing to the first basis vector  less than u1xe2x80x2 greater than  and the second basis vector  less than u2xe2x80x2 greater than .
FIG. 3 is three-dimensionally drawn. The third base extraction vector  less than u3 greater than  is subjected to orthogonal transform processing to the first basis vector  less than u1xe2x80x2 greater than  to obtain an intermediate orthogonal vector  less than u3xe2x80x3 greater than .
[Numeral 3]                              u          3          xe2x80x3                =                              u            3                    -                                                    ⟨                                                      u                    1                    xe2x80x2                                    ·                                      u                    3                                                  ⟩                                                              "LeftDoubleBracketingBar"                                      u                    1                    xe2x80x2                                    "RightDoubleBracketingBar"                                2                                      ⁢                          u              1              xe2x80x2                                                          (        3        )            
Further, the intermediate orthogonal vector  less than u3xe2x80x3 greater than  is subjected to orthogonal transform processing to the second basis vector  less than u2xe2x80x2 greater than  to obtain the third basis vector  less than u3xe2x80x2 greater than .
[Numeral 4]                                                                        u                3                xe2x80x2                            =                                                u                  3                  xe2x80x3                                -                                                                            ⟨                                                                        u                          2                          xe2x80x2                                                ·                                                  u                          3                          xe2x80x3                                                                    ⟩                                                                                      "LeftDoubleBracketingBar"                                                  u                          2                          xe2x80x2                                                "RightDoubleBracketingBar"                                            2                                                        ⁢                                      u                    2                    xe2x80x2                                                                                                                          =                                                (                                                            u                      3                                        -                                                                                            ⟨                                                                                    u                              1                              xe2x80x2                                                        ·                                                          u                              3                                                                                ⟩                                                                                                      "LeftDoubleBracketingBar"                                                          u                              1                              xe2x80x2                                                        "RightDoubleBracketingBar"                                                    2                                                                    ⁢                                              u                        1                        xe2x80x2                                                                              )                                -                                                                            ⟨                                                                        (                                                                                    u                              3                                                        -                                                                                                                            ⟨                                                                                                            u                                      1                                      xe2x80x2                                                                        ·                                                                          u                                      3                                                                                                        ⟩                                                                                                                                      "LeftDoubleBracketingBar"                                                                          u                                      1                                      xe2x80x2                                                                        "RightDoubleBracketingBar"                                                                    2                                                                                            ⁢                                                              u                                1                                xe2x80x2                                                                                                              )                                                ·                                                  u                          2                          xe2x80x2                                                                    ⟩                                                                                      "LeftDoubleBracketingBar"                                                  u                          2                          xe2x80x2                                                "RightDoubleBracketingBar"                                            2                                                        ⁢                                      u                    2                    xe2x80x2                                                                                                                          =                                                u                  1                                -                                                                            ⟨                                                                        u                          1                          xe2x80x2                                                ·                                                  u                          3                                                                    ⟩                                                                                      "LeftDoubleBracketingBar"                                                  u                          1                          xe2x80x2                                                "RightDoubleBracketingBar"                                            2                                                        ⁢                                      u                    1                    xe2x80x2                                                  -                                                                            ⟨                                                                        u                          2                          xe2x80x2                                                ·                                                  u                          3                                                                    ⟩                                                                                      "LeftDoubleBracketingBar"                                                  u                          2                          xe2x80x2                                                "RightDoubleBracketingBar"                                            2                                                        ⁢                                      u                    2                    xe2x80x2                                                                                                          (        4        )            
Turning to FIG. 2, in step S126, a scalar coefficient xcex1i is calculated using the orthogonal vector  less than uixe2x80x2 greater than  so that a distance with the differential vector  less than dk greater than  (at first  less than dj greater than ) becomes minimum.
FIG. 3(C) is an image drawing of the orthogonal transform processing. In FIG. 3(C), where a differential vector represented by  less than dk greater than  is subjected to approximation, a square norm thereof (ei=∥ less than dk greater than xe2x88x92xcex1i less than uixe2x80x2 greater than ∥2 ) is minimum when the product of the orthogonal vector  less than uixe2x80x2 greater than  and the scalar coefficient xcex1i is diagonal with the differential vector { less than dk greater than xe2x88x92xcex1i  less than uixe2x80x2 greater than } as shown in FIG. 3(C) (inner product=0). Accordingly, the scalar coefficient xcex1i is obtained by the formula (5).
[Numeral 5]                                          ⟨                                          α                i                            ⁢                                                u                  i                  xe2x80x2                                ·                                  (                                                            d                      k                                        ⁢                                          –α                      i                                        ⁢                                          u                      1                      xe2x80x2                                                        )                                                      ⟩                    =          0                ⁢                  
                ⁢                                                            α                i                            ⁢                              ⟨                                                      u                    i                    xe2x80x2                                    ·                                      d                    k                                                  ⟩                                      -                                          α                i                2                            ⁢                              ⟨                                                      u                    i                    xe2x80x2                                    ·                                      u                    i                    xe2x80x2                                                  ⟩                                              =          0                                    (5-1)                                          α          i                =                              ⟨                                          d                k                            ·                              u                i                xe2x80x2                                      ⟩                                              "LeftDoubleBracketingBar"                              u                i                xe2x80x2                            "RightDoubleBracketingBar"                        2                                              (5-2)            
It is shown in the drawing that the differential vector  less than dk greater than  (k=0) is subjected to approximation to other first base extraction vector  less than ujxe2x80x2 greater than . The first base extraction vector  less than ujxe2x80x2 greater than  is shown by the image drawing because it can take optional directions.
Turning to FIG. 2, in step S127, a square norm (ei) of error vector is obtained by the formula (6) after the differential vector  less than dk greater than (k=0) is subjected to approximation to the base extraction vector xcex1i less than ujxe2x80x2 greater than .
[Numeral 6]                                                                        e                i                            =                                                "LeftDoubleBracketingBar"                                                            d                      k                                        -                                                                  α                        i                                            ⁢                                              u                        i                        xe2x80x2                                                                              "RightDoubleBracketingBar"                                2                                                                                        =                                                                    "LeftDoubleBracketingBar"                                          d                      k                                        "RightDoubleBracketingBar"                                    2                                -                                  2                  ⁢                                      α                    i                                    ⁢                                      ⟨                                                                  d                        k                                            ·                                              u                        i                        xe2x80x2                                                              ⟩                                                  +                                                      α                    i                    2                                    ⁢                                                            "LeftDoubleBracketingBar"                                              u                        i                        xe2x80x2                                            "RightDoubleBracketingBar"                                        2                                                                                                                          =                                                                    "LeftDoubleBracketingBar"                                          d                      k                                        "RightDoubleBracketingBar"                                    2                                -                                  2                  ⁢                                                                                    ⟨                                                                              d                            k                                                    ·                                                      u                            i                            xe2x80x2                                                                          ⟩                                            2                                                                                      "LeftDoubleBracketingBar"                                                  u                          i                          xe2x80x2                                                "RightDoubleBracketingBar"                                            2                                                                      +                                                                                                    ⟨                                                                              d                            k                                                    ·                                                      u                            i                            xe2x80x2                                                                          ⟩                                            2                                                                                      "LeftDoubleBracketingBar"                                                  u                          i                          xe2x80x2                                                "RightDoubleBracketingBar"                                            4                                                        ⁢                                                            "LeftDoubleBracketingBar"                                              u                        i                        xe2x80x2                                            "RightDoubleBracketingBar"                                        2                                                                                                                          =                                                                    "LeftDoubleBracketingBar"                                          d                      k                                        "RightDoubleBracketingBar"                                    2                                -                                                                            ⟨                                                                        d                          k                                                ·                                                  u                          i                          xe2x80x2                                                                    ⟩                                        2                                                                              "LeftDoubleBracketingBar"                                              u                        i                        xe2x80x2                                            "RightDoubleBracketingBar"                                        2                                                                                                                          =                              E                -                                                                            ⟨                                                                        d                          k                                                ·                                                  u                          i                          xe2x80x2                                                                    ⟩                                        2                                                                              "LeftDoubleBracketingBar"                                              u                        i                        xe2x80x2                                            "RightDoubleBracketingBar"                                        2                                                                                                          (        4        )            
In step S128 of FIG. 2, it is judged whether ei is less than Exe2x80x2 or not. If ei is less than Exe2x80x2, content of Exe2x80x2 is renewal in step S129 and the information regarding xcex1i,  less than uixe2x80x2 greater than ,  less than ui greater than , etc. at the time is held in an arrangement [xcex1k], [ukxe2x80x2], [uk], etc. If ei is not less than Exe2x80x2, the processing in step S129 is skipped.
In step S130, one (1) is added to the counter i, and in step S131, it is judged whether i is not less than N (=8192) or not. If i is less than N. turning to step 124 and the same processing is carried out with respect to next base extraction vector  less than ui greater than .
The processing is repeated and when it is judged in step S131 that i is not less than N, all base extraction vectors  less than ui greater than  have been completely tried. At the time, the register Exe2x80x2 holds the minimum square norm ei.
It is judged in step S132 whether Exe2x80x2 is not more than Z or not. If Exe2x80x2 is more than Z, it is treated as E=Exe2x80x2 in step S133. That is, the square norm of the differential vector is renewal. In step S134, one (1) is added to the counter k, turning to step S122. If Exe2x80x2 is not more than Z, this processing is skipped. Thus, the orthogonal basis xcex1k less than ukxe2x80x2 greater than (k=1xcx9cm) to approximate the difference of the first differential vector  less than dj greater than  to the allowable error Z is obtained.
However, the block mean value ai of the base extraction block  less than Ui greater than  has been rounded off or down in the conventional methods and therefore, improvement of image quality is limited. Why the conventional methods are inconvenient will be explained according to FIG. 4.
FIG. 4 is an image drawing of mean value separation processing. A relationship of base extraction block  less than Ui greater than  (vertical axis) with the pixel value of certain row (horizontal axis) is shown in FIG. 4(a). An actual pixel value is a block mean value of 16 pixels, but the block mean value of 4 pixels will be used to simplify the explanation herein. In FIG. 14(a), each pixel value is 5, 2, 4, and 3 and its mean value ai is 3.5, when the first decimal place is round down, the block mean value ai of the base extraction block  less than ui greater than  is 0.5 as shown in FIG. 4(b). In FIG. 4(c), if the basis vector xcex2k  less than uk greater than  is added to the DC value DCJ of the decoded block, the DC component (ai=0.5) is overlapped on the target block  less than Rj greater than . In case that the number of basis is plural, the DC value is overlapped on the DCJ by various values in the range of 0 less than ai less than 1, and as a result, certain noise is overlapped per each block in the decoded image, whereby image quality is not improved. This disadvantage also occurs in case that the first decimal place is rounded off or up.
According to the conventional AOT processing, much operations and much time are required, because all of the base extraction vectors  less than ui greater than  must be subjected to orthogonal processing to the preceding base vectors  less than ukxe2x80x2 greater than .
It is therefore an object of the invention to provide an image encoding/decoding method, which provides high image quality at high speed, an apparatus thereof and a recording medium in which such program therefor is recorded.
The above object of the invention can be solved by the construction, for example, as shown in FIG. 5. That is, the image encoding method of the invention (1) comprises producing a DC image composed of each block mean value by dividing an image data per B pixel into a block, making a part of said DC image a DC nest, and where the differential vector  less than dj greater than  which is obtained by separating the DC value DCJ from the pixel block to be encoded is over an allowable value Z, calculating one or more orthogonal basis (e.g. xcex1k less than vk greater than ), to which the differential vector  less than dj greater than  is approximated, by the adaptive orthogonal transform (AOT) using the DC nest, wherein the lowest n (n=log2 B) bits of the DC pixel in each sample being set to 0, where the base extraction block is down-sampled from the DC nest and the block mean value ai of it is calculated using the samples.
Accordingly, any fraction less than 1 does not occurs in the block mean value ai and the block mean value ai with integer level precision is obtained at high speed.
In a preferred embodiment of the invention (1) that is the invention (2), the lowest n bits of the DC pixel is set to 0 or is masked, where the DC nest is produced from the DC image.
Accordingly, the DC nest, of which the lowest n bits of the DC pixel is set to 0 or is masked, is efficiently obtained by one processing.
In a preferred embodiment of the invention (1) or (2) that is the invention (3), a base extraction vector  less than ui greater than  is produced to which the differential vector  less than dj greater than  approximates by separating the block mean value ai from the base extraction block  less than Ui greater than  in which the lowest n bits of the DC pixel is set to 0.
According to the invention (3), the sum (the block mean value) of all elements in such base extraction vectors  less than ui greater than  is always 0 and the DC component is completely separated. Therefore, even if the base vectors  less than uk greater than  are piled up on each other in the decoding side, unnecessary DC component (noise) does not cause. The image quality in the HVQ system is more improved by the invention (3).
In a preferred embodiment of the invention (3) that is the invention (4), optional elements (e.g. u16) of base extraction vectors  less than ui greater than  are replaced by linear bond of the remainder elements and the inner product of the base extraction vectors  less than ui greater than  and the other optional vectors  less than w greater than  are calculated by the formula.
 less than wxc2x7ui greater than =(w1xe2x88x92w16)ui+(w2xe2x88x92w16)u2+ . . . +(w15xe2x88x92w16)u15 
In the invention (4), the sum of all elements in the base extraction vectors  less than ui greater than  is always 0 and hence, the optional elements (e.g. u16) are represented by the linear bond of the remainder elements. Accordingly, the inner product calculation  less than wxc2x7ui greater than  with the other optional vectors (w) can be expanded to the product-sum calculation as shown by the above formula, whereby a single round of such complicated calculation can be omitted. Since much inner product calculation of the vectors is conducted in the image encoding method according to the HVQ system, such single round omission of the calculation contributes to high speed encoding processing.
In a preferred embodiment of the invention (3) or (4) that is the invention (5), a first basis is searched so that hi may be maximum in the following formula,
hi= less than dxc2x7ui greater than 2/∥ui∥2 
wherein  less than d greater than  is the differential vectors and  less than ui greater than  is the base extraction vectors.
According to the invention (5), such condition that square norm ∥ less than d greater than xe2x88x92 less than xcex1i ui greater than ∥2 of the difference with the differential vectors  less than d greater than  is minimum can be searched by the above simple calculation. Hence, the AOT processing can be carried out at high speed.
In the invention (6), a second basis is searched so that hi may be maximum in the following formula,
hi={ less than dxc2x7ui greater than xe2x88x92( less than dxc2x7u1 greater than  less than u1xc2x7ui greater than /∥u1∥2)2/{∥ui∥2xe2x88x92( less than u1xc2x7ui greater than )/∥u1∥2}
wherein  less than d greater than  is the differential vectors,  less than u1 greater than  is the base extraction vectors corresponding to the first basis, and  less than ui greater than  is the base extraction vectors for searching the second basis in the invention (3) or (4).
According to the invention (6), the AOT processing can be done more efficiently and at higher speed in addition to the advantages of the invention (5), because the calculation result which has been obtained in the first basis search can be used with respect to  less than dxc2x7u1 greater than  and ∥u1∥ of the numerator, and ∥ui∥2 and ∥u1∥ of the denominator.
In a preferred embodiment of the invention (3) or (4) that is the invention (7), a third basis is searched so that hi may be maximum in the following formula,
hi=( less than dxc2x7ui greater than xe2x88x92 less than dxc2x7v1 greater than  less than v1xc2x7ui greater than xe2x88x92 less than dxc2x7v2 greater than  less than v2xc2x7u1 greater than )2/{∥ui∥2xe2x88x92 less than v1xc2x7ui greater than 2xe2x88x92 less than v2xc2x7ui greater than 2}
wherein  less than d greater than  is the differential vectors,  less than v1 greater than  is the first orthonormal base vectors,  less than v2 greater than  is the second orthonormal base vectors, and  less than ui greater than  is the base extraction vectors for searching the third basis.
According to the invention (7), the AOT processing can be done more efficiently and at higher speed in addition to the advantages of the invention (5) and (6), because the calculation result which has been obtained in the first and second basis search can be used with respect to ( less than dxc2x7ui greater than xe2x88x92 less than dxc2x7v1 greater than  less than v1xc2x7ui greater than ) of the numerator, and (∥ui∥2xe2x88x92 less than v1xc2x7ui greater than 2) of the denominator.
In a preferred embodiment of the invention (6) or (7) that is the invention (8), the base extraction vectors  less than ui greater than  which match with search conditions are subjected to orthogonal transform with one or more preceding orthonormal basis.
That is, one orthonormal processing per each base extraction vector  less than ui greater than , which is adopted as the basis after the search termination at each stage is carried out, whereby the AOT processing can be done more efficiently and at higher speed.
In the image encoding method of the invention (9), the norm of each scalar expansion coefficient xcex21xcx9cxcex2m is rearranged in decreasing order, a difference (including 0) between norms adjacent to each other is calculated, and Huffman coding is applied to the obtained difference. In the method, the basis is represented by xcex2k less than uk greater than , wherein k=1xcx9cm.
In general, the norm of each scalar expansion coefficient xcex21xcx9cxcex2m can take various value. When the value is rearranged in ascending or descending order and the difference (including 0) between norms adjacent to each other is calculated, each difference is often similar to or same as each other. The more encoding compression is possible by applying the Huffman coding to the difference value.
In the image encoding method of the invention (10), image data  less than Rj greater than  of coding objective block is encoded instead of the coding of the basis, where the basis is more than certain number. Accordingly, the decoded image quality is improved. In practical, it does not affect the coding compression ratio because such situation is little.
The above object of the invention can be resolved by the construction, for example, as shown in FIG. 14. That is, the image decoding method of the invention (11) comprises reproducing a DC image corresponding to each block mean value per B pixel from encoding data with respect to the HVQ system, making a part of said DC image a DC nest, reproducing image data  less than Rj greater than  of target block by synthesizing, to DC value DCJ of target block, one or more basis vectors xcex2k less than uk greater than  which is selected from DC nests based on the encoding data, and the lowest n (n=log2 B) bits of the DC pixel in each sample is set to 0, where the selected block is down-sampled from the DC nest and the block mean value of it is calculated using the samples.
Accordingly, any fraction less than 1 does not occurs in the block mean value and the block mean value with integer level precision is obtained at high speed.
According to the image decoding method in the invention (12), where the decoded basis is information with respect to xcex2k less than uk greater than  (k=1xcx9cm), the lowest n (n=log2 B) bits of the DC pixel per each selected block (Uk) to be read out from the DC nest are set to 0, product-sum calculation of basis xcex2k less than uk greater than  (k=1xcx9cm) is carried out, and the calculated result is divided by the number B of block pixels.
In the invention (12), the lowest n bits of each selected block (Uk) are set to 0, and hence, even if these are accumulated and added, the addition result becomes multiple of integer of the block size B (e.g. 16). An expansion coefficient xcex2k is an integer precision. Accordingly, if the cumulative addition result is divided by the number B of the block pixels, block mean value Aj is efficiently obtained by one processing. Therefore, such calculation that the basis vectors xcex2k less than uk greater than  (k=1xcx9cm) are overlapped can be effectively carried out.
In a preferred embodiment of the invention (11) or (12) that is the invention (13), the lowest n bits of each DC pixel is set to 0, where DC nests are produced from the DC image, whereby processing is effectively carried out.
The image encoding apparatus of the invention (14) comprises producing a DC image composed of each block mean value by dividing an image data per B pixel into a block, making a part of said DC image a DC nest, and where a differential vector  less than dj greater than  which is obtained by separating the DC value DCJ from the pixel block to be encoded is over an allowable value Z, calculating one or more orthogonal basis ( e.g. xcex1k less than vk greater than ), to which the differential vector  less than dj greater than  is approximated, by the adaptive orthogonal transform (AOT) using the DC nest, and providing a memory 17 to store the DC nest in which the lowest n (n=log2 B) bits of the DC pixel are set to 0.
The image decoding apparatus of the invention (15) comprises reproducing a DC image corresponding to each block mean value per B pixel from encoding data with respect to the HVQ system, making a part of said DC image a DC nest, reproducing image data less than Rj greater than  of target block by synthesizing, to the DC value DC, of target block, one or more basis vectors xcex2k less than uk greater than  which is selected from DC nests based on the encoding data, and providing a memory 49 to store the DC nest in which the lowest n (n=log2 B) bits of the DC pixel are set to 0.
The recording medium of the invention (16) comprises a computer readable recording medium storing a program to make a computer to implement the processing described in one of the invention (1) to (13).